package letcode.problem.dynamicProgra;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/minimum-falling-path-sum/description/?envType=study-plan-v2&envId=dynamic-programming
 * */
public class MinimumFallingPath {
    /**
     *
     代码
     测试用例
     测试用例
     测试结果
     931. 下降路径最小和
     中等
     相关标签
     相关企业
     给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

     下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
     * */
    public static int minFallingPathSum(int[][] matrix) {
        int x = matrix.length;
        int y = matrix[0].length;
        int[][] f = new int[x][y];
        for (int i = 0; i < y; i++) {
            f[0][i] = matrix[0][i];
        }
        if (x == 1 && y == 1) {
            return matrix[0][0];
        }
        for (int i = 1; i < x; i++) {
            for (int i1 = 0; i1 < y; i1++) {
                int left = Math.max(i1 - 1, 0);
                int right = Math.min(i1 + 1, y - 1);
                f[i][i1] = Math.min(f[i - 1][right], Math.min(f[i - 1][left], f[i - 1][i1])) + matrix[i][i1];
            }
        }

        return Arrays.stream(f[x - 1]).min().orElse(0);
    }

    public static void main(String[] args) {
        System.out.println(
                minFallingPathSum(
                        new int[][]{
                                {100,-42,-46,-41},
                                {31,97,10,-10},
                                {-58,-51,82,89},
                                {51,81,69,-51}
                        }
                )
        );
    }


}
